//
//  739_每日温度.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/9.
/**
 https://leetcode.cn/problems/daily-temperatures/description/
 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

 示例 1:
 输入: temperatures = [73,74,75,71,69,72,76,73]
 输出: [1,1,4,2,1,1,0,0]
 示例 2:

 输入: temperatures = [30,40,50,60]
 输出: [1,1,1,0]
 示例 3:

 输入: temperatures = [30,60,90]
 输出: [1,1,0]
 */

import UIKit

class  GetDailyDay {
    
    func QA() {
        print(dailyTemperatures([73,74,75,71,69,72,76,73]))
        print(dailyTemperatures([30,40,50,60]))
        print(dailyTemperatures([30,60,90]))
        print("------------")
        print(dailyTemperatures1([73,74,75,71,69,72,76,73]))
        print(dailyTemperatures1([30,40,50,60]))
        print(dailyTemperatures1([30,60,90]))

    }
    
    /// 暴力法
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        if temperatures.count == 0 {
            return []
        }
        var resultArray = Array(repeating: 0, count: temperatures.count)
        for index in (0...temperatures.count - 2).reversed() {
            var j = index + 1
            let item = temperatures[index]
            while j < temperatures.count {
                if temperatures[j] > item {
                    resultArray[index] = j - index
                    break
                }
                j += 1
            }
        }
        
        return resultArray
    }
    
    /// 类似动态规划解法
    func dailyTemperatures1(_ temperatures: [Int]) -> [Int] {

        if temperatures.count == 0 {
            return []
        }
        var rightParents = Array(repeating: 0, count: temperatures.count)
        var stack = [Int]() // 依次递减栈
        for i in 0..<temperatures.count {
            while !stack.isEmpty, let topIndex = stack.last, temperatures[i] > temperatures[topIndex] {
                rightParents[topIndex] = i - topIndex
                stack.removeLast()
            }
            stack.append(i)
        }
        return rightParents
    }
}
